﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        vector<bool> f(amount + 1); // 建表
        // 建表
        dp[0] = 1;
        f[0] = true;
        for (auto x : coins)                  // 拿出物品
            for (int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
                f[j] = f[j] || f[j - x];
        if (f[amount] == false)
            return 0;                         // 初始化
        for (auto x : coins)                  // 拿出物品
            for (int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
                dp[j] += dp[j - x];
        return dp[amount];
    }
};